package Midium;

import java.util.Comparator;
import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

public class Solution1482 {
    public int minDays(int[] bloomDay, int m, int k) {
        // 优化：
        // 不需要定义flower数组，不然超出空间限制，每次只需要从bloomDay里找有没有m组连续k个比a小的数
        // a就是set里从小到大的每一个数
        // 超出时间限制了，还需要优化
        // 我不要从set[0]开始取值，而是从set[set.size()/2]开始取值进行判断，因为如果第三天可以了，那么第三天以后的一定也可以
        // 相当于在set里找一个数，顺着找是O(N)级别，二分查找是O(log_2 N)级别
        if (m * k > bloomDay.length) return -1;
        /*
            flower[i][j]表示第i天的时候，第j朵花是否开放 1为开放，0为不开放
            遍历所有可能的i（从bloomDay中选）,如果能找到m组连续的k个 flower[i][j] == true 则返回i
            最后也没找到就返回-1
        */
        Set set = new TreeSet(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                return (int) o1 - (int) o2;
            }
        });
        for (int i = 0; i < bloomDay.length; i++) {
            set.add(bloomDay[i]); // 存放可能出现的第几小时开花
        }
        Object[] unreapetDay = set.toArray();

        // 看看第几小时能满足要求
        // 题目保证一定有结果
        int i = 0;
        int j = unreapetDay.length - 1;
        int mid = (j-i) / 2 +i;

        while(i < j){
            int hour = (int) unreapetDay[mid];
            // 在flower中寻找是否有连续的m组的k个1
            int mSum = 0;
            int kSum = 0;
            boolean flag = true;
            for (int p = 0; p < bloomDay.length; p++) {
                if (bloomDay[p] <= hour) {
                    kSum++;
                    if (kSum == k) {
                        kSum = 0;
                        mSum++;
                        if (mSum == m) {
                            j = mid;
                            mid = (j-i) / 2 +i;
                            flag = false;
                            continue;
                        }
                    }
                } else {
                    kSum = 0;
                }
            }if(flag) {
                i = mid + 1;
                mid = (j - i) / 2 + i;
            }
        }
        return (int)unreapetDay[mid];
    }

    public int minDay(int[] bloomDay, int m, int k) {
        if (m * k > bloomDay.length) return -1;
        /*
            flower[i][j]表示第i天的时候，第j朵花是否开放 1为开放，0为不开放
            遍历所有可能的i（从bloomDay中选）,如果能找到m组连续的k个 flower[i][j] == true 则返回i
            最后也没找到就返回-1
        */
        Set set = new TreeSet(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                return (int) o1 - (int) o2;
            }
        });
        for (int i = 0; i < bloomDay.length; i++) {
            set.add(bloomDay[i]); // 存放可能出现的第几小时开花
        }
        Object[] unreapetDay = set.toArray();
        int[][] flower = new int[unreapetDay.length][bloomDay.length];
        for (int i = 0; i < unreapetDay.length; i++) {
            int j = (int) unreapetDay[i];
            // 看看哪朵花第j天开,这里有一个i与j的对应关系 需要注意不要搞混了
            for (int p = 0; p < bloomDay.length; p++) {
                if (i > 0) {
                    flower[i][p] = flower[i - 1][p]; // 前几天开过的花，今天当然也还开着
                }
                if (bloomDay[p] == j) {
                    flower[i][p] = 1;
                }
            }
        }
        // 看看第几小时能满足要求
        for (int i = 0; i < unreapetDay.length; i++) {
            int j = (int) unreapetDay[i];
            // 在flower中寻找是否有连续的m组的k个1
            int mSum = 0;
            int kSum = 0;
            for (int p = 0; p < bloomDay.length; p++) {
                if (flower[i][p] == 1) {
                    kSum++;
                    if (kSum == k) {
                        kSum = 0;
                        mSum++;
                        if (mSum == m)
                            return j;
                    }
                } else {
                    kSum = 0;
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Solution1482 s = new Solution1482();
        int i = s.minDays(new int[]{1, 10, 3, 10, 2}, 3, 1);
        System.out.println(i);
    }
}
